package com.leetcode.根据数据结构分类.链表;

import com.leetcode.datastructure.ListNode;

import java.util.HashSet;

/**
 * @author: ZhouBert
 * @date: 2020/11/19
 * @description: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
 * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
 * --
 */
public class A_83_删除排序链表中的重复元素 {

	/**
	 * 分析：
	 * 在 203 的基础之上，可以利用哨兵节点；
	 * 又根据“重复”的要求，可以利用哈希算法-HashSet
	 * 这个解法其实没有考虑这是个“排序”列表！
	 *
	 * @param head
	 * @return
	 */
	public ListNode deleteDuplicates(ListNode head) {
		//当只有一个节点，或者没有节点的时候->直接返回
		if (head == null || head.next == null) {
			return head;
		}
		//1.构建一个哨兵
		ListNode guard = new ListNode(-1);
		guard.next = head;
		//2.构建一个 HashSet
		HashSet<Integer> set = new HashSet<Integer>();
		//3.构建必要的节点
		ListNode pre = guard;
		ListNode cur = head;
		while (cur != null) {
			//如果已经重复
			if (set.contains(cur.val)) {
				pre.next = cur.next;
			} else {
				pre = pre.next;
				set.add(cur.val);
			}
			cur = cur.next;
		}
		return guard.next;
	}

	/**
	 * 由于删除重复元素，所以必定头元素保留！->用不着哨兵！
	 *
	 * @param head
	 * @return
	 */
	public ListNode deleteDuplicates2(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode cur = head;
		while (cur != null && cur.next != null) {
			//满足删除的条件 -> 删除下一个节点
			if (cur.val == cur.next.val) {
				cur.next = cur.next.next;
				//[如果进行了删除，那么是不需要移动 cur 指针的！]
			}else {
				cur = cur.next;
			}
		}
		return head;
	}

	public static void main(String[] args) {

	}
}
